
class Hello1{

static int N=1000;	
	
public static int[] initArr(){
	int[] arr=new int[N];
	for(int i=1;i<N;i++){
		arr[i]=(int) (N*Math.random());
	}
	return arr;	
}
	
public static void showArr(int[] arr){
	for(int i=1;i<N;i++){
	System.out.print(arr[i]+" ");
	}
}

public static int[] shakerSort(int[] arr){
	int i,j,copy;
	boolean sw;
	for(i=1;i<N;i++){
		sw=false;
		for(j=i;j<N-i;j++){
		if(arr[j]>arr[j+1]){
			copy=arr[j];
			arr[j]=arr[j+1];
			arr[j+1]=copy;
		}
		}
		for(j=N-i;j>i;j--){
		if(arr[j]<arr[j-1]){
			copy=arr[j];
			arr[j]=arr[j-1];
			arr[j-1]=copy;
			sw=true;
		}	
		}
	if(!sw)break;
	}
	return arr;
}

public static boolean check(int[] arr){
	int i;
	boolean res=true;
	for(i=1;i<N-1;i++){
		if(arr[i]>arr[i+1])res=false;
	}
	return res;
}

public static void main(String[] args){ 
	int[] array=initArr();
	showArr(array);
	System.out.println(check(array));
	showArr(shakerSort(array));
	System.out.println(check(array));
	
} 

}